Solutions for the automated optimizing and transitioning of placements of multiple virtual machines (VMs), e.g., Xen® VMs (www.Xen.org) in a computing environment have only recently begun to be addressed by the industry, Current VMware® virtualization software products, such as Virtualization Infrastructure (VI) provide technology for enabling automated VM placement. However, none of the existing products is known to include a technology that uses similar concepts to those described in the present invention for automatic generation of a plan for changing the current placement of virtual machines in a datacenter of distributed computing resources into a given desired (target) placement. Moreover the resulting plan adheres to a set of constraints in the sense that no temporal state of deployment during plan execution (i.e., after the execution of each plan step) may violate a constraint.
US20050198244A1 entitled “Automatic provisioning of services based on a high level description and an infrastructure description” does not describe the placement of VMs in environments having distributed computing resources but to a deployment technique for provisioning of services. This reference describes generating a plan to allow deployment of a new service and then executing the plan. The plan generation aims to achieve a new resource allocation state that includes the new service. The plan implements an unordered set of provision actions whose application is restricted by preconditions, e.g., plan steps, whose application is restricted by policies and resource constraints. The described technique executes a forward-chaining type algorithm in its “Back End Generation” stage. However, there are several fundamental differences. First, the referenced technique is not based on a model of VMs, so it lacks the logic for generating VM-specific operations, such as “relocate”, “suspend”, etc. Also, being ignorant of migrations/relocations (that are not part of the service model), the referenced technique does not detect or resolve “migration cycles”. Last, the referenced technique does not employ specific time-conserving optimizations (such as “follow the change”, see below) that are not applicable to the service context in general but do apply to the VM placement model of the present invention.
US20050204358 describes a technique that addresses planning and scheduling change management requests in computing systems by calculating an optimal ordering of a set of tasks with certain inter-dependencies imposed by constraints such as collocation, anti-location (“exlocation”) and resource capacity restrictions. This technique, however, is suited for scheduling of tasks for execution at servers, one at a time, for limited period of times, unlike the placement of VMs, which are placed effectively forever (unless a change is required), and that groups of VMs may be placed on the same server at the same time. Last, the referenced technique is tailored for specific types of constraints (collocation, exlocation, etc). In contrast, the present invention can be applied to any constraint that can be defined as a predicate function that can be evaluated over a placement.
US20070094670A1 entitled “Method and an apparatus for providing automatic emergency mode plan generation in a utility computing environment” describes a technique for automatically identifying types of failing resources that are required to a critical service and replacing them with matching resources that are allocated from reserve pools or confiscated from less critical services. It involves plan generation for resource allocation, but does not consider order of steps and does not deal with migration/allocation cycles.
US20060224550A1 entitled “Policy Based Resource Management for Legacy Data” describes a technique for moving data among storage resources according to specific policies. Again, while directed to automated planning, it does not deal with resource allocation, but rather migrating data to storage locations according to specific criteria.
It is understood that there are trivial solutions to the automated plan for changing a current VM placement, i.e., (re)placing VMs: for example, the operations involved in changing the placement may be executed in arbitrary order or, all together at the same time. These trivial solutions can easily result in illegal temporary states, however, such as overloading a host beyond its resource capacity, or placing multiple VMs on the same host despite a policy that forbids them from sharing a host.
Thus, while the concepts of automated planning, resource allocation, goal-driven planning (to reach from state A to state B) and ordering steps according to dependencies have been studied, there does not appear to be any prior art describing a solution for building a model for VM placement that facilitates the generation of an appropriate placement plan that avoids violating policies/constraints, and, additionally that accounts for migration cycles.
Moreover, neither the patent nor non-patent literature addresses observing migration cycles caused by policies, much less the concept of abusing a VM for breaking migration cycles. In the domain of virtual machines (e.g., Xen VMs, VMware VMs, etc), “abusing” a VM (i.e., make it release its assigned resources), is unlike abusing a process (that typically needs to be killed) or a transaction (that needs to be rolled back), in the sense that a VM can be simply suspended to an image form (that holds no runtime resources) or migrated/relocated to another host, without losing its state.
It would be highly desirable to provide a Virtual Machine Placement Planning (VMPP) system and method implementing a VMPP model for automatically generating a plan for changing a current placement of resource-consuming virtual entities, e.g., virtual machines in a computing environment, e.g., a datacenter or a cloud of distributed computing resources, into a given desired (target) placement.
It would be highly desirable that the system and method changes placement of virtual machines in computing environments from a first placement state into a given desired (target) placement state in a manner that is safe with respect to a set of VM-related constraints. That is, the plan should guarantee that no constraint is violated during its execution (i.e., after each step is executed).
It would be highly desirable to provide a virtual machine (VM) placement planning system and method implementing a VMPP model that assumes a server or like host device can execute more than one VM at the same time.